package medium不同路径;

import org.testng.annotations.Test;

public class Solution {
    public int uniquePaths(int m, int n) {
        int[] a={0};
        Path(m,n,a);
        return a[0];
    }
    //组合数学
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
    //动态规划
    public int uniquePaths1(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
    public void Path(int m, int n,int[] a){
        if (m==1 || n==1){
            a[0] = a[0]+ Math.min(m,n);
            return;
        }
        else if (m==2 || n==2){
            a[0] = a[0]+ Math.max(m,n);
            return;
        }
        Path(m-1,n,a);
        Path(m,n-1,a);
    }
    @Test
    public void test(){
        System.out.println(uniquePaths(4,4));
    }




}
